home *** CD-ROM | disk | FTP | other *** search
/ Aminet 28 / Aminet 28 (1998)(GTI - Schatztruhe)[!][Dec 1998].iso / Aminet / game / board / Exchess.lha / EXChess / sort.cpp < prev    next >
C/C++ Source or Header  |  1998-05-23  |  2KB  |  111 lines
  1. /*-------------------------- Sorting Routines ------------------------*/
  2. //  This is a collection of sorting routines from various sources
  3. //  The Insert Sort seems to be the fastest for these applications
  4. //  and it is also a "stable" sort - which is desirable
  5.  
  6. #include "chess.h"
  7. #include "define.h"
  8. #include "const.h"
  9. #include "funct.h"
  10.  
  11. typedef move_rec T;
  12. typedef move_rec TblIndex;
  13. #define CompGT(a,b) (a < b)
  14.  
  15. void InsertSort(T *Lb, T *Ub);
  16. void ShellSort(T *Lb, T *Ub);
  17. void QuickSort(T *Lb, T *Ub);
  18.  
  19.  
  20. void Sort(move_rec *Lb, move_rec *Ub)
  21. {
  22.    InsertSort(Lb, Ub);
  23. }
  24.  
  25. /* -------------- Insert Sort Routine ---------------------*/
  26.  
  27. void InsertSort (T *Lb, T *Ub) {
  28.    T V, *I, *J, *Jmin;
  29.    /**********************
  30.    *  Sort Array(Lb..Ub) *
  31.    **********************/
  32.    Jmin = Lb - 1;
  33.    for (I = Lb + 1; I <= Ub; I++) {
  34.        V = *I;
  35.        for ( J = I-1; J != Jmin && CompGT(J->score,V.score); J--)
  36.        *(J+1) = *J;
  37.        *(J+1) = V;
  38.    }
  39. }
  40.  
  41. void ShellSort (T *Lb, T *Ub) {
  42.   int inc = 1; T V, *I, *J;
  43.   do {
  44.      inc *= 3;
  45.      inc++;
  46.   } while (inc <= Ub - Lb);
  47.   do {
  48.      inc /= 3;
  49.      for (I = Lb+inc; I <= Ub; I++) {
  50.          V = *I;
  51.          J = I;
  52.          while ((J-inc)->score < V.score) {
  53.              *J = *(J-inc);
  54.               J -= inc;
  55.               if ((J-Lb) < inc) break;
  56.          }
  57.          *J = V;
  58.      }
  59.   } while (inc > 1);
  60. }
  61.  
  62. /*------------------- Quick Sort Routine --------------------*/
  63.  
  64. T *Partition(T *Lb, T *Ub) {
  65.     T  V, Pivot, *I, *J, *P;
  66.  
  67.     unsigned int Offset;
  68.  
  69.     Offset = (Ub - Lb)>>1;
  70.     P = Lb + Offset;
  71.     Pivot = *P;
  72.     *P = *Lb;
  73.  
  74.     I = Lb + 1;
  75.     J = Ub;
  76.     while (1) {
  77.     while (I < J && CompGT(Pivot.score, I->score)) I++;
  78.     while (J >= I && CompGT(J->score, Pivot.score)) J--;
  79.  
  80.     if (I >= J) break;
  81.     V = *I;
  82.     *I = *J;
  83.     *J = V;
  84.     J--; I++;
  85.     }
  86.  
  87.     *Lb = *J;
  88.     *J = Pivot;
  89.  
  90.     return J;
  91. }
  92.  
  93. void QuickSort(T *Lb, T *Ub) {
  94.     T *M;
  95.  
  96.     while (Lb < Ub) {
  97.  
  98.       M = Partition (Lb, Ub);
  99.  
  100.       if (M - Lb <= Ub - M) {
  101.       QuickSort(Lb, M-1);
  102.       Lb = M+1;
  103.       } else {
  104.       QuickSort(M+1, Ub);
  105.       Ub = M - 1;
  106.       }
  107.    }
  108. }
  109.  
  110.  
  111.